package com.zh.note.huawei.twohundred.找单词;

import java.util.Deque;
import java.util.LinkedList;

/**
 * https://dream.blog.csdn.net/article/details/132019140
 */
public class Main {
    public static void main(String[] args) {
        // Scanner sc = new Scanner(System.in);
        // int n = sc.nextInt();
        // String[][] matrix = new String[n][n];
        // for (int i = 0; i < n; i++) {
        //     for (int j = 0; j < n; j++) {
        //         matrix[i][j] = sc.next();
        //     }
        // }
        // String target = sc.next();
        int n = 4;
        String[][] matrix = {{"A", "C", "C", "F"}, {"C", "D", "E", "D"}, {"B", "E", "S", "S"}, {"F", "E", "C", "A"}};
        String target = "ACCESS";
        // 1、双层循环遍历每一个节点
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                Deque<Integer[]> path = new LinkedList<>();
                if (dfs(i, j, 0, path, matrix, target, n)) {
                    printPath(path);
                    return;
                }
            }
        }
        System.out.println("NO");

    }

    private static void printPath(Deque<Integer[]> path) {
        StringBuilder sb = new StringBuilder();
        for (Integer[] pos : path) {
            sb.append(pos[0]).append(",").append(pos[1]).append(",");
        }
        //去掉最后一个逗号
        System.out.println(sb.substring(0, sb.length() - 1));
    }

    //index是target字符下标
    private static boolean dfs(int i, int j, int index, Deque<Integer[]> path, String[][] matrix, String target, int n) {
        if (index >= target.length()) {
            return false;
        }
        String temp = target.substring(index, index + 1);
        if (i < 0 || i >= n || j < 0 || j >= n || !temp.equals(matrix[i][j])) {
            return false;
        }

        if (path.size() == target.length()) {
            return true;
        }
        path.add(new Integer[]{i, j});

        boolean res = dfs(i - 1, j, index + 1, path, matrix, target, n)
                || dfs(i, j - 1, index + 1, path, matrix, target, n)
                || dfs(i, j + 1, index + 1, path, matrix, target, n)
                || dfs(i + 1, j, index + 1, path, matrix, target, n);

        return res;

    }
}
